<?php
namespace Units;
/**
 * 路线规划类
 * Class RoutePlanner
 */
class RoutePlanner
{
    private $data = [];   //原始数据
    private $maxStops =17;  //最大站数
    private $maxWeight = 6600; //最大重量
    private $routerAveragePoints; //平均每条路线站数
    private $routers = []; //规划路线容器
    private $maxLat;
    private $minLat;
    private $maxLng;
    private $minLng;
    private $latPartitionValue;   //每个区域的间隔lat值
    private $lngPartitionValue;   //每个区域的间隔lng值
    private $currentRouteKey = 1;  //当前规划的路由id
    function __construct( $data )
    {
        $this->data =  $data;
    }

    /**
     * 画一个四边形分成9块，把对应的点放进相应的区域（顺序 1->2->3->6->5->4->7->8->9->2）
     * @return array   返回最终规划路线结果
     */
    public  function chunk()
    {

        $this->data = $this->sortByfield($this->data , 'lat');
        $this->minLat = $this->data[0]['lat'];
        $this->maxLat = end($this->data)['lat'];
        $this->data = $this->sortByfield($this->data, 'lng');
        $this->minLng = $this->data[0]['lng'];
        $this->maxLng = end($this->data)['lng'];

        $this->latPartitionValue = sprintf( "%.4f" , ( $this->maxLat - $this->minLat ) / 3);
        $this->lngPartitionValue = sprintf( "%.4f" , ( $this->maxLng - $this->minLng ) / 3);
        $this->routerAveragePoints = $this->getRouterAveragePoints();
        $len = $this->getRouterNum();
        foreach ($this->data as $item) {
            $key = $this->getSquareNum( $item );
            //lat lng 要保留两位小数
            $item['lng'] = sprintf( "%.4f" ,$item['lng']);
            $item['lat'] = sprintf( "%.4f" ,$item['lat']);
            $this->routers[$key][] = $item;
        }

        $arr =[1,2,3,6,5,4,7,8,9];
        foreach ($arr as $item ) {
            if(!empty($this->routers[$item])){
                $this->dispatch($item);
            }
        }
        return $this->routers;

    }

    /**
     * 获取某一个点在九宫格的位置
     * @param $point
     * @return float|int
     */
    private function getSquareNum( $point ){

        if($point['lng'] != $this->minLng && $point['lng'] != $this->maxLng){
            $offsetLng = ceil( ($point['lng'] - $this->minLng) / $this->lngPartitionValue );
        }elseif ($point['lng'] == $this->minLng) {
            $offsetLng = 1;
        }else{
            $offsetLng = 3;
        }
        if( $point['lat'] != $this->minLat && $point['lat'] != $this->maxLat ){
            $offsetLat = ceil( ($point['lat'] - $this->minLat) / $this->latPartitionValue );
        }elseif ($point['lat'] == $this->minLat) {
            $offsetLat =1;
        }else{
            $offsetLat =3;
        }
        return  ( 3 * ( $offsetLat - 1 ) ) + $offsetLng;
    }

    /**
     * 获取路线的数量
     * @return float
     */
    private function getRouterNum()
    {
        $len = count( $this->data );
        return ceil( $len / $this->maxStops );
    }

    /**
     * 设置当前操作的路由id
     * @param $i
     */
    private function setCurrentRouteKey( $i )
    {
        $this->currentRouteKey = $i;
    }
    /**
     * 获取当前操作的路由id
     * @param $i
     */
    private function getCurrentRouteKey( )
    {
        return $this->currentRouteKey;
    }

    /**
     * 调度和分配路由
     * @param $i 当前区域的顺序
     * @return bool
     */
    private function dispatch( $i )
    {
        $this->setCurrentRouteKey( $i );
        $stops = 0;
        $weight = 0;
        $routers = [];
        if(empty($this->routers[$i])){
            return false;
        }
        $this->routers[$i] = $this->sequencePoints( $this->routers[$i] , $i);
        $copy = $this->routers[$i];
        $next = $this->getNeighbour( $i );
        foreach ($copy as $key => $value) {
            $stops++;
            $weight = $weight + $value['GrossWeight'];
            if( $stops<= $this->routerAveragePoints && $weight <= $this->maxWeight) {
                $routers[] = $value;
                unset($copy[$i]);
            }else{
                if($next){
                    $this->routers[$next][] = $value;
                }else{
                    $this->routers[10][] = $value;
                }
            }
        }
        $this->routers[$i] = $routers;
        if( $i < 9 ) {
            $this->pushPointsFromNext( $next  );
        }

    }

    /**
     * 从下一个相邻的区域放进当前的区域
     * @param $i 下一个区域序号
     * @return bool
     */
    private function pushPointsFromNext($i)
    {
        $routeKey = $this->getCurrentRouteKey();
        $weightAndStops = $this->getWeightAndStops($this->routers[$routeKey]);
        $stops = $weightAndStops['stops'];
        $weight = $weightAndStops['weight'];
        $routers = [];
        $next = $this->getNeighbour( $i );
        if(empty($this->routers[ $i ]))
        {
            $next && $this->pushPointsFromNext( $next );
            return false;
        }
        $this->routers[ $i ] = $this->sequencePoints( $this->routers[ $i ] , $i );
        foreach ($this->routers[ $i ] as $key => $value) {
            $stops++;
            $weight = $weight + $value['GrossWeight'];
            if( $stops<= $this->routerAveragePoints && $weight <= $this->maxWeight) {
                $routers[] = $value;
                unset($this->routers[$i][$key]);
            }
        }
        if(empty($this->routers[$i])){
            unset($this->routers[$i]);
        }
        $this->routers[$routeKey] = array_merge( $this->routers[$routeKey]  , $routers );
        $next = $this->getSquareNum( $next );
        $this->pushPointsFromNext( $next );

    }

    /**
     * 获取站数和重量
     * @param $data
     * @return array
     */
    private function getWeightAndStops( $data ) {
        $len = count( $data );
        $weight = 0;
        for( $i=0 ;$i < $len ;$i++ ) {
            $weight = $weight + $data[$i]['GrossWeight'];
        }
        return ['stops'=>$len,'weight'=>$weight];
    }
    private function  getNeighbour( $i) {

        switch ($i) {
            case '1':
                return 2;
                break;
            case '2':
                return 3;
                break;
            case '3':
                return 6;
                break;
            case '6':
                return 5;
                break;
            case '5':
                return 4;
                break;
            case '4':
                return 7;
                break;
            case '7':
                return 8;
                break;
            case '8':
                return 9;
                break;
            case '9':
                return false;
                break;

        }

    }

    /**
     * 在区域内按照距离排序
     * @param $data
     * @param $i
     * @return mixed
     */
    private function  sequencePoints($data , $i) {

        $col = ( $i % 3);
        $row = ceil( $i / 3);
        if( $row ==1 && $col !=0  ) {  //1,2
            return $this->sortByfield($data ,'lng');//SORT_DESC
        }
        if( $row ==1 && $col ==0  ) {  //3
            return $this->sortByfield($data ,'lat');
        }
        if(  $row ==2 && $col !=1 ){ //4,5
            return $this->sortByfield($data ,'lng','SORT_DESC');
        }
        if( $row ==2 && $col ==1 ) { //6
            return $this->sortByfield($data ,'lat');
        }
        if( $row ==3  ) {
            return $this->sortByfield($data ,'lng');
        }

    }

    /**
     * 获取每条路线的平局站数
     * @return float
     */
    private function getRouterAveragePoints()
    {
        return floor(  count( $this->data ) / $this->getRouterNum());
    }

    /**
     * 排序
     * @param $arrUsers
     * @param $field
     * @param string $direction
     * @return mixed
     */
    private function sortByfield($arrUsers,$field,$direction='SORT_ASC')
    {

        $sort = array(
            'direction' => $direction, //æåºé¡ºåºæ å¿ SORT_DESC éåºï¼SORT_ASC ååº
            'field'     => $field, //æåºå­æ®µ
        );
        $arrSort = array();
        foreach($arrUsers AS $uniqid => $row){
            foreach($row AS $key=>$value){
                $arrSort[$key][$uniqid] = $value;
            }
        }
        if($sort['direction']){
            array_multisort($arrSort[$sort['field']], constant($sort['direction']), $arrUsers);
        }
        return $arrUsers;
    }

    /**
     * 检查是否所有的点分配到路线上
     * @return bool
     */
    public function checkIsAllDispatch()
    {
        if( empty( $this-> routers ) )
        {
            return true;
        }
        return $this->getUnAssignPoints();
    }

    /**
     * 获取分配路线的点
     * @return array
     */
    private function getUnAssignPoints(){
        $ret = [];

        foreach ( $this->routers  as $item )
        {
            array_merge( $ret, $item);
        }
        return $ret;
    }

}